import jdk.internal.org.objectweb.asm.tree.IincInsnNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Created by L.jp
 * Description:请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

 * 示例1:
 *
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 
 * User: 86189
 * Date: 2022-11-30
 * Time: 8:50
 */
public class Solution {
    //滑动窗口，使用哈希表存储字符判断是否重复字符
    /*
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0){
            return 0;
        }
        Set<Character> set=new HashSet<>();
        int max=0;
        //set就是窗口
        for(int i = 0,j=0; j <s.length(); j++){
            char c = s.charAt(j);
            //包含了重复值就缩小窗口，左边缩小
            while (set.contains(c)){
                set.remove( s.charAt(i++) );
            }
            //不包含重复字符，那么就加入字符
            set.add( c );
            //更新最长不重复字符的长度
            max=Math.max( max, j-i+1);

        }
        return max;
        
       }
       */
    
    
    //动态规划
    public int lengthOfLongestSubstring(String s) {
        if(s.length()<=0 || s==null){
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        //以i下标结尾的字符串的最长无重复子字符串
        int[] dp=new int[s.length()];
        //0到0下标长度就是1
        dp[0]=1;
        //先把第一个字符的位置和字符放入哈希表
        map.put( s.charAt( 0 ),0 );
        int max=1;
        for(int i=1;i<s.length();i++){
            //如果没有重复字符，那么当前的转态就等于前一个状态+1
            if(!map.containsKey( s.charAt( i ) )){
                dp[i]=dp[i-1]+1;
            }else{
                //有重复的，就要求出不重复区间的长度，首先要知道上一次出现该字符的位置
                int lastIndex=map.get( s.charAt( i ) );
                //判断上一次该字符出现的位置是在，上一个无重复的字符串区间之内还是之外
                //判断方法就是用上一个无重复的字符串区间的长度，该字符当前的位置减去上一次出现该字符的位置代表这一次的无重复区间，这两者对比
                dp[i]=dp[i-1]<i-lastIndex ? dp[i-1]+1 : i-lastIndex; //如果是等于的话，应该取后者
            }
            max=Math.max(max,dp[i]);
            //存储当前位置和当前位置的字符
            map.put( s.charAt( i ),i );
        }
        return max;
    }
    //优化，使用动态规划，dp[j]表示字符串以j结尾的字符串的最长无重复子串
    //使用哈希表记录当前该字符出现的最近的一个位置i，i位置之后到j的区间就是最长无重复子串的长度
    /*
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        //res记录最终结果，tmp记录当前位置的最长长度
        int res = 0, tmp = 0;
        for(int j = 0; j < s.length(); j++) {
            int i = dic.getOrDefault(s.charAt(j), -1); // 获取上一次出现的最近的位置i
            dic.put(s.charAt(j), j); // 放入当前位置和字符，更新哈希表
            //如果前一个位置的最长长度小于无重复区间的长度，那么当前位置的最长长度就等于前一个位置的最长长度+1
            //如果是大于的话，那么就是无重复区间的长度
            //dp[i]=dp[i-1]<j-i ? dp[j-1]+1 : j-i
            tmp = tmp < j - i ? tmp + 1 : j - i;
            // max(dp[j], dp[j-1])
            res = Math.max(res, tmp);
        }
        return res;
    }
    */
    
}
